/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 */

// @lc code=start
class Solution {
    public String longestPalindrome(String s) {

        // 1.暴力解法
        // int len = s.length();
        // if(len < 2) {
        //     return s;
        // }

        // int maxLength = 0;
        // int begin = 0;

        // char[] chars = s.toCharArray();

        // for(int i = 0; i < len - 1; i++) {
        //     for(int j=i+maxLength; j < len; j++) {
        //         if(fit(chars, i, j) && j-i+1 > maxLength) {
        //         maxLength = j-i+1;
        //         begin = i;
        //         }
        //     }
            
        // }

        
        // 2. 动态规划
        // int len = s.length();
        // if(len < 2) {
        //     return s;
        // }
        // int maxLength = 1;
        // int begin = 0;

        // boolean[][] dp = new boolean[len][len];
        // char[] chars = s.toCharArray();

        // for(int i = 0; i < len; i++) {
        //     dp[i][i] = true;
        // }

        // for(int j = 1; j < len; j++) {
        //     for(int i = 0; i < j; i++) {
        //         if(chars[i] != chars[j]) {
        //             dp[i][j] = false;
        //         } else {
        //             if(j - i < 2) {
        //                 dp[i][j] = true;
        //             } else {
        //                 dp[i][j] = dp[i+1][j-1];
        //             }
        //         }

        //         if(dp[i][j] && j-i+1 > maxLength) {
        //             maxLength = j-i+1;
        //             begin = i;
        //         }
        //     }
        // }
        // return s.substring(begin, begin + maxLength);



        // 动态规划
        int len = s.length();
        if(s == null || len < 2) {
            return s;
        }

        int res = 1;
        int begin = 0, end = 0;

        boolean[][] dp = new boolean[len][len];

        for(int r = 1; r < len; r++) {
            for(int l = 0; l < r; l++) {
                if(s.charAt(l) == s.charAt(r) && (r-l <= 2 || dp[l+1][r-1])) {
                    dp[l][r] = true;
                    if(r-l+1 > res) {
                        res = r-l+1;
                        begin = l;
                        end = r;
                    }
                }
            }
        }
        return s.substring(begin, end+1);



 
    }

    // private boolean fit(char[] chars, int left, int right) {
    //     while(left <= right) {
    //         if(chars[left] != chars[right]) {
    //             return false;
    //         }
    //         left++;
    //         right--;
    //     }
    //     return true;
    // }


    




}
// @lc code=end

